Skip to main content

BM14 链表的奇偶重排

描述

给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。注意是节点的编号而非节点的数值。

{1,2,3,4,5,6}
{1,3,5,2,4,6}

题解

我自己原本是想使用一个单独的指针来进行拆分,但发现边界条件难以判断,同时代码也很复杂

/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func oddEvenList(head *ListNode) *ListNode {
// write code here
if head == nil {
return nil
}
var odd, even, evenHead, oddHead *ListNode
odd = head
even = head.Next
evenHead = &ListNode{
Val: 0,
}
oddHead = &ListNode{
Val: 0,
}
nowEven := evenHead
nowOdd := oddHead
for odd.Next != nil && even.Next != nil {
nowOdd.Next = odd
nowEven.Next = even
odd = odd.Next.Next
even = even.Next.Next
nowOdd = nowOdd.Next
nowEven = nowEven.Next
}
if odd.Next == nil {
nowOdd.Next = odd
odd = odd.Next.Next
nowOdd = nowOdd.Next
nowOdd.Next = nil
} else {
nowOdd.Next = odd
nowEven.Next = even
nowOdd = nowOdd.Next
nowEven = nowEven.Next
nowOdd.Next = nil
nowEven.Next=nil
}

evenHead = evenHead.Next
oddHead = oddHead.Next
nowOdd.Next=evenHead
return oddHead

}

查看官方答案,发现直接进行了双指针复用的,即奇数的下一个数一定是偶数。

package main

import . "nc_tools"

/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/

/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func oddEvenList(head *ListNode) *ListNode {
// 如果链表为空或者只有一个节点,直接返回
if head == nil || head.Next == nil {
return head
}
// 奇数节点的头节点
odd := head
// 偶数节点的头节点
even := head.Next
// 保存偶数节点的头节点,用于后续拼接
evenHead := even

// 遍历链表,分离奇数节点和偶数节点
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
// 将奇数节点链表的末尾连接到偶数节点链表的头部
odd.Next = evenHead

return head

}